package tree.递归;

import po.TreeNode;

/**
 * @author songZiHao
 * @version 1.0.0
 * @ClassName N完全二叉树的节点个数222.java
 * @Description TODO https://leetcode-cn.com/problems/count-complete-tree-nodes/
 * @createTime 2021年04月14日 09:56:00
 */
public class N完全二叉树的节点个数222 {


    public int countNodes(TreeNode root) {
        if (root == null) {
            return 0;
        }
        //先计算树的高度 h
        int high = treeHigh(root);
        //计算右子树的高度
        int rightHigh = treeHigh(root.right);
        if (rightHigh == high - 1) {
            //如果    右子树的高度  =  h-1  , 说明   左子树  是完美二叉树,可以通过公式(2^(h-1))-1计算即可，不需要全部遍历
            return (1 << (high - 1)) + countNodes(root.right);
        } else {
            //如果    右子树的高度  ≠  h-1  ，说明   右子树  是完美二叉树。可以通过公式(2^(h-1))-1计算即可，不需要全部遍历，只不过比上面那种少了一层，h-2
            return (1 << (high - 2)) + countNodes(root.left);
        }
    }

    private int treeHigh(TreeNode root) {
        int high = 0;
        while (root != null) {
            high++;
            root = root.left;
        }
        return high;
    }

    public int countNodes2(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return countNodes2(root.left) + countNodes2(root.right) + 1;
    }
}
